package com.yulongtian.offers.day202211.day20221103;

import java.math.BigInteger;

/**
 * https://leetcode.cn/problems/jian-sheng-zi-ii-lcof/?favorite=xb9nqhhg
 * 勉强过
 *
 * @author yulongTian
 * @create 2022-11-03 14:20
 */
public class Test01 {
    public static void main(String[] args) {
        System.out.println(cuttingRope(200));
    }

    public static int cuttingRope(int n) {
        if (n == 2) {
            return 1;
        }

        if (n == 3) {
            return 2;
        }

        if (n == 4) {
            return 4;
        }

        if (n == 5) {
            return 6;
        }

        if (n == 6) {
            return 9;
        }

        BigInteger[] arr = new BigInteger[n + 1];

        arr[2] = BigInteger.valueOf(1);
        arr[3] = BigInteger.valueOf(2);
        arr[4] = BigInteger.valueOf(4);
        arr[5] = BigInteger.valueOf(6);
        arr[6] = BigInteger.valueOf(9);


        for (int i = 7; i < n + 1; i++) {
            for (int j = 1; j < 5; j++) {
                if (arr[i - j].multiply(BigInteger.valueOf(j)).compareTo(arr[i - j - 1].multiply(BigInteger.valueOf(j + 1))) == 1) {
                    arr[i] = arr[i - j].multiply(BigInteger.valueOf(j));
                    break;
                }
            }
        }

        return arr[n].mod(BigInteger.valueOf(1000000007)).intValue();
    }
}
